import java.util.Arrays;

public class question_31 {
}
class Solution_31 {
    public void nextPermutation(int[] nums) {
//        特殊情况
        if(nums.length==1){
            return;
        }
        int n=nums.length;
//        index用来记录从后往前第一个不是递增序列的位置
        int index=-1;
//        从最后一个数开始遍历
        for (int i =n-1 ; i >0; i--) {
            if(nums[i-1]<nums[i]){
                index=i-1;
                break;
            }
        }

        if(index==-1){
//            整个数组都是递增的，则需要重新按从小到大排序，也就是已经到头了
            Arrays.sort(nums);
        }else{
//            先将index位置的数与后面第一个大于index位置的数字进行交换，交换后再将index后面位置的数字进行排序，按升序拍
            for (int i = n-1; i>index ; i--) {
                if(nums[i]>nums[index]){
//                    交换
                    int temp=nums[i];
                    nums[i]=nums[index];
                    nums[index]=temp;
                    break;
                }
            }
//            排序，后半部分
            Arrays.sort(nums,index+1,n);
        }
    }

    public static void main(String[] args) {
        Solution_31 solution_31=new Solution_31();
        int arr[]={1,3,2};
        solution_31.nextPermutation(arr);
    }
}
